In a location aware device system, such as a cellular telephone system, new services are being offered beyond simple calls, messaging and internet connectivity. For example, these new services may require running a proxy on a server for each telephone user which may hold the state of one or more application sessions, maintain the sessions through periods of wireless disconnection, and provide transcoding appropriate for the given phone type or location aware device. For example, transcoding may be required when clients want to check accounts, access information and make purchases with their cellular phones, personal digital assistant, or some other location aware device. Web applications designed to take advantage of rendering capabilities of desktop browsers do not generally render effectively on the small screens of cellular phones or personal digital assistants. Some devices have little or no graphics capability, or require different markup languages, such as Wireless Markup Language (WML) for text presentation. Transcoding is technology for adapting content to match constraints and preferences associated with specific environments. For a description of dynamic transcoding methodologies, see “Transcoding: Extending e-business to new environments,” Britton et al., IBM Systems Journal, Vol. 40, No. 1, 2001.
Servers providing the above described services are assigned based upon geographic area. The problem is that servers handling these functions can become overloaded when too many clients use these services in a geographical area.
FIG. 1A depicts an example of a geographic map showing a road network and three cities. Cellular phone users will travel within the geographic area for such reasons as commuting to work and attending events in halls or sports arenas. Such travel may concentrate a larger than normal number of cellular phone users in a relatively small geographic area. Furthermore, usage may increase during lunch hours or during breaks in concerts or half-times at athletic events. In addition, not only will the number of cell phone users increase within the geographic area, but also demands for delivery of information from available information delivery subsystems will increase. For the foregoing reasons, telecommunication servers assigned to one geographic area may have significant increases and decreases in usage during different periods of time due to the migration of cellular phone users within the geographic area. It is desirable to have a means for automatically changing the geographic boundaries of the areas assigned to servers to more evenly distribute the demands on the servers in the system.
Balancing of server workload may be accomplished by moving the geographic boundaries of server assignments. U.S. Pat. No. 5,630,129 (the '129 patent) discloses the use of tiles and tiling to balance loads within “neighborhoods.” The '129 patent states that the method steps are referred to as “tiling” and that “[i]n tiling, the definition of a neighborhood is extended to include all processors whose elements are neighbors of elements in the center processor. Neighborhood is defmed as “a processor at the center of a circle of some predetermined radius and all other processors within the circle.” Processors in a neighborhood are “balanced with respect to each other using local (as opposed to global) performance measurements.” (4:9-24). In addition, the '129 patent states “the tiling method redistributes the work so that processors containing elements on the domain boundary have fewer elements than those in the interior of the domain.” (11:61-64).
In addition, servers handling telecommunication functions require intra-system communications between servers to update data based on changes in client locations and application usage. For example, as a client moves from one geographic area to the next, the client may be assigned to a new server and information regarding the client may be relevant to other location aware device users and to other applications. Existing cellular telephone systems are adept at transferring clients from one geographic area to another. But a solution to automatic scalability must also address synchronization of information between servers. Moreover, the need for distributing demand on servers in a telecommunications system can be extended to include all location aware communication devices from which clients may access applications while changing locations within a geographic area.
One area where analogous development regarding user movement has taken place is in the implementation of multi-player on-line games. Multi-player on-line games require updated data for each user location and application that a user may call upon during game play. FIG. 1B is a depiction of a game scenario in which three players interact. As shown in FIG. 1B, players A, B and C initially begin in areas where they do not have visual contact with each other in the virtual world map. But after players A, B and C move into the upper right comer of the virtual world map, players A and C are in virtual line of sight with each other and players B and C are in virtual line of sight with each other. Depending on the game type, players A, B and C may call upon the application they are participating in to perform various actions. The complexity of calculations and server demand increases as the number of players increases. In addition, as the number of players in a portion of the game area increases, the number of calculations called upon to be made increases.
New games attempt to avoid server overload by having dynamic boundaries. However, in these implementations, there are many places in the game space where players can simultaneously see into one or more other servers' area of control. Thus, the servers need to synchronize information with their neighbors. Furthermore, these implementations use a “grey” area around the partitioning boundaries where both servers partially “own” the objects and the data is mirrored between the servers. The mirroring of data is an attempt to reduce the work involved in handing off an object to the next server when the object leaves the grey area. This mirroring, though, further increases synchronization problems and greatly complicates the server code. These techniques are described in “Massively Multi-player Game Development” edited by Thor Alexander 2003 (ISBN 1-58450-243-6). The book states the many difficulties with this approach, yet states that it is necessary to achieve scalability. For further information see “Practical Grid Computing for Massively Multiplayer Games” by Levine et al. 2003 (ISBN 1-58450-292-4).
Thus, a method for dynamically reassigning server boundaries without using “grey areas” is needed. Such a method should have automatic scalability so that it can adapt to any number of clients (for example 10 to 10,000); should allow clients to be reassigned to a different server in order to balance loads; and should be able to dynamically distort the server-to-geography mapping in response to usage “hot-spots” without increasing the time required for a signal to travel from one point on the network to another.
As discussed above, multi-player virtual game developments may be examined for solutions to load-balancing problems for clients using location aware devices to access information systems. However, in a multi-player game environment, a client is assigned statically to a game server for the life of the game. Clients cannot move from one server to the next without a substantial change to the server infrastructure. It would be advantageous to combine the use of proxy servers, as known in the telecommunications art and in the virtual game art, to a method for dynamically distorting server-to-geography mapping as discussed above, so that the substantial changes to the server infrastructure can be avoided.